class Solution {
    public int reversePairs(int[] record) {
        /**
         * 数组中的逆序对
         *  解法2：使用归并排序
         *  思路：
         *      1，将数组分为a、b两部分，分别计算a、b区间的逆序对，再从a、b中任选一个元素计算逆序对（）*/
        return mergeSort(0, record.length-1, record);
    }

    public static int[] tempArray = new int[5_0000];

    public static int mergeSort(int left, int right, int[] nums) {
        // 1 递归出口
        if(left >= right) {
            return 0;
        }
        // 2 设定划分点（偏左中心）
        int mid = left + (right - left) / 2;
        // 3 计算左右逆序对
        int answer = 0;
        answer += mergeSort(left, mid, nums);
        answer += mergeSort(mid+1, right, nums);
        // 4 计算a、b区间联合逆序对并排序
        int n = right - left + 1;
        int baseIndex = left;
        // -临时存储
        int left2 = mid + 1;
        int index = 0;
        while(left <= mid && left2 <= right) {
            if(nums[left] <= nums[left2]) {
                tempArray[index++] = nums[left++];
            } else {
                answer += (mid - left + 1);
                tempArray[index++] = nums[left2++];
            }
        }
        while(left <= mid) {
            tempArray[index++] = nums[left++];
        }
        while(left2 <= right) {
            tempArray[index++] = nums[left2++];
        }
        // -实际写入
        for(int i = 0; i < n; i++) {
            nums[baseIndex + i] = tempArray[i];
        }
        // 5 返回值
        return answer;
    }
}